package com.algrithom.sort;

import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 * 386. 字典序排数
 */
public class Solution1 {
    public static void main(String[] args){
        Solution1 solution1 = new Solution1();
        System.out.println(solution1.lexicalOrder(13));
        System.out.println(solution1.lexicalOrder2(13));
    }

    public List<Integer> lexicalOrder(int n) {
        Set<Integer> result = new TreeSet<>((o1,o2) -> {
            String str1 = String.valueOf(o1);
            String str2 = String.valueOf(o2);
            return str1.compareTo(str2);
        });
        for (int i=1;i<=n;i++) {
            result.add(i);
        }
        return new LinkedList<>(result);
    }
    public List<Integer> lexicalOrder2(int n) {
        List<Integer> result = new LinkedList<>();
        for (int i=1;i<10;i++) {
            dfs(i,n,result);
        }
        return result;
    }

    private void dfs(int val,int target,List<Integer> path) {
        if (val > target) {
            return;
        }
        path.add(val);
        int start = val * 10;
        int i = start;
        while (i < start + 10) {
            dfs(i++,target,path);
        }
    }
}
